package com.azdebugit.java8.suanfa.zijie;

import org.apache.commons.lang3.RandomStringUtils;
import org.junit.Test;

import java.util.*;
public class Solution {
    
    /**
     * 思路：
     * （1）首先对数组进行排序（从小到大）
     * （2）依次取出第 i 个数（i从0开始），并且不重复的选取（跳过重复的数）
     * （3）这样问题就转换为 2 个数求和的问题（可以用双指针解决方法）
     * ==》数求和问题
     * （4）定义两个指针：左指针（left） 和 右指针（right）
     * （5）找出固定 left， 此时left所指的位置为数组中最小数，再找到两个数和 不大于 target 的最大 right 的位置
     * （6）调整 left 的位置（后移），求解和是否为 target O(n)
     * ==》时间复杂度：O(nlogn) + O(n)
     * @param
     */
    @Test
    public void streamRandomStriTest() {
        String s = RandomStringUtils.randomAlphanumeric(10);
        System.out.println("----------"+s);
        int[] num = new int[]{1,2,3,5,6,7,8,-1,-2,-3,-5,-6,-7,-8};
        threeSum(num).stream().forEach(x->{
            System.out.println();
            x.stream().forEach(System.out::print);
        });

    }
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
 
        if(num==null || num.length<3){
            return res;
        }
        Arrays.sort(num);// 排序
        for(int i=0;i<num.length-2;i++){
            if(num[i]>0){
                break;// 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            }
            if(i>0 && num[i]==num[i-1]){
                continue;// 去重
            }
            int L=i+1;
            int R=num.length-1;
 
            while(L<R){
                int sum=num[i]+num[L]+num[R];
                if(sum==0){
                    ArrayList<Integer> list=new ArrayList<>();
                    list.add(num[i]);
                    list.add(num[L]);
                    list.add(num[R]);
                    res.add(list);
 
                    while(L<R && num[L]==num[L+1]){
                        L++;
                    }
                    while(L<R && num[R]==num[R-1]){
                        R--;
                    }
                    L++;
                    R--;
                }
                else if(sum>0){
                    R--;
                }
                else if(sum<0){
                    L++;
                }
            }
        }
        return res;
    }
}